# define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>


struct Node {
    int val;
    struct Node* next;
    struct Node* random;
    
};

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur = head;
    while (cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        struct Node* next = cur->next;
        //copy->random=NULL;

        cur->next = copy;
        copy->next = next;

        cur = next;
    }
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = cur->next->next;
    }

    struct Node* newhead = NULL, * copytail = NULL;
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if (newhead == NULL)
        {
            newhead = copytail = copy;
        }
        else
        {
            copytail->next = copy;
            copytail = copytail->next;
        }
        cur->next = next;
        cur = next;
    }
    return newhead;
}

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;


        if (fast == slow)
        {
            struct ListNode* cur = fast, * prev = head;
            int pos = -1;


            while (prev != cur)
            {
                prev = prev->next;
                cur = cur->next;
                pos++;
            }
            return prev;
        }
    }
    return NULL;
}